COMMENT ⊗   VALID 00015 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00003 00002	%2
C00006 00003	Our primitive domain consists of objects called atoms or atomic symbols.
C00009 00004	.BEGIN INDENT 0TABS 20,39TURN ON "\"NOFILL
C00012 00005	.GROUP
C00015 00006	We have two functions for traversing binary trees.  They are both partial functions
C00018 00007	We cannot generate a very exciting theory based simply on %3car, cdr,%* and %3cons
C00022 00008	%3
C00025 00009	Here's an intuitive description of such a function (predicate named %3equal%*).
C00027 00010	.GROUP
C00032 00011	.NEXT PAGE
C00035 00012	%1
C00037 00013	.APART
C00039 00014	.BEGIN TURN ON "←,\"NOFILLTABS 10,25,36
C00042 00015	.BEGIN TURN ON "←,\"TABS 10
C00044 ENDMK
C⊗;
%2
.TURN ON "←";
←LISP - a high-level mathematical language for data structures.
.TURN OFF "←";
%1

Just as it is unnecessary to learn machine language to study numerical
algorithms, it is also unnecessary to learn machine language to understand
non-numerical processes.  The distinction we are making is between data-
structures and storage structures.  That is, data structures are independent
of %6how%* they are implemented on a machine.  Data structures are representations
of information chosen to exhibit certain ordering and accessibility relation-
ship between data structures.  Certainly in the real world you cannot ignore
storage structures when you are deciding upon the data structures which
will encode your problem, but the interesting aspects of representation of
information can be discussed at the level of data structures with no loss
of generality.  The mapping of data structures to storage structures is
machine dependent anyway, and consists of bit-pushing, trickery and black
magic.  A very crucial problem in data structures and algorithms is the
interplay between the representation and the algorithm:  if you pick a
frugal representation prhaps your accessing algorithms become more time
consuming or the algorithm become less general.  We will study this
interrelation carefully in this course.

If you take a course in elementary number theory or better yet recursive
function theory, you would begin with a precise description of the domain
of interest (the non-negative integers perhaps, or 0 and the successor
function) and then describe the class of functions or operations which will
be allowed in the developing theory. We will do the same.


Our primitive domain consists of objects called atoms or atomic symbols.
In computer science terminolgy they are either identifiers or numbers; i.e.
.GROUP SKIP 2;
.BEGIN INDENT 0; TURN ON "\";NOFILL;TABS 13;
.GROUP;
<atom>\:: = <identifier>|<number>
<identifier>\:: = <letter>|<identifier><letter>|<identifier><digit>
<number>\:: = <digit>|<number><digit>
<letter>\:: =%3 A |B |C ...| Z%*
<digit>\:: = %30 |1 |2 ... |9%*
.APART;
.END;
.GROUP SKIP 2;
.BEGIN INDENT 0;TURN ON "\";NOFILL;TABS 20,35;DOUBLE SPACE;
.GROUP;
For example:\atoms\not atoms
%3\ABC123\2a
\12\a
\A4D6\$$g
\NIL\ABD.
\T\(A . B)
%*
.APART;
.END;

Using an operator to be described later, we are able to enlarge on
this primitive domain obtaining the domain of interest for LISP functions,
that is the class of %6symbolic expressions%* or %6S-expressions%* or also called
%6S-exprs%*.  S-exprs include as a proper subset the atoms, but S-exprs can be
constructed of other S-exprs as follows:  a left-paren followed by an
S-expr, followed by a period, followed by an S-expr, followed by a
period, followed by an S-expr, followed by a right-paren is also an S-expr.
To make everyone happy here's a BNF definition of S-expr
.TURN ON "←";

←<sexpr> :: = <atom>|%3(%*<sexpr> . <sexpr>%3) |( )%*

.TURN OFF "←";
We added "%3( )%*" as an S-expr for a reason which will become clear later.


.BEGIN INDENT 0;TABS 20,39;TURN ON "\";NOFILL;
.GROUP;
Examples:\S-exprs\not S-exprs
%3
\A\A . B
\(A . B)\(A . B . C)
\(((A.B) .C) . (A.B))\((A . B)))
%*
.APART;
.END;
.GROUP SKIP 2;
Non-atomic sexprs are also called %6dotted-pairs%*.  S-exprs have a natural
interpretation as binary trees.  A binary tree is a branching structure 
consisting of a single root node and perhaps a collection of terminal
and non-terminal nodes.  From non-terminal nodes we sprout exactly two
branches; no branches are grown from the terminal nodes.  And most
important:  there are no intersecting branches.  We will alk about more
general structures later (called list-structures or directed graphs).
.GROUP SKIP 2;
.GROUP;
Here are some binary tres:

%3
.BEGIN VERBATIM;

					.		  
		       			A
	                 			    	A  


	1  2	 					B      NIL


		A   	D     E



		B    C

.END
.APART;
%1
Perhaps you can see how to interpret S-exprs now.  The atoms are
interpreted as terminal nodes;  and since non-atomic S-exprs always
have two branches (oops, two sub-expressions) we can write the first
sub-expression as the left branch of a binary tree and the second sub-
expression as the right branch.  
.GROUP SKIP 2;
.GROUP;
For example:

%3
.BEGIN VERBATIM;
	(A . B)				(A . (B . C))



				       A   

	 A  B				 
					B    C


.APART;

.GROUP;





	((A . B) . C)			(A . (B . NIL))





	  	C			A  


     A      B				    B      NIL

.APART;
.END
%1
Other representations of binary trees which will be more suggestive when
we talk about implementation of LISP are:
%3
.GROUP
.BEGIN VERBATIM

(A . (B . C))



 ≡        A             ≡                                 ≡ 

	                          A            B     C 


	      B    C  						A




								   B        C

.END;
.APART

%6Note that the translation process is inherently recursive.
%1
.group skip 2;
So much for the domain of objects;  what we need now are some functions
or operators to perform oprations on the domain.  First such function is the
%3cons%* (construct) function wwich is used to generate s-exprs from less
complicated s-exprs.  %3cons%* is a total function, that is it is defined for all
sexpr arguments. It is a function of two arguments and has as value a
new sexpr interpreted as a binary tree with left branch as the first argument
and with right branch, the second argument.  For example:

.BEGIN NOFILL;TURN ON "←";
←%3cons[A; B] = (A . B)

←cons[(A . B); C] = ((A . B) .C)
.END;
%1

.GROUP SKIP 2;
We have two functions for traversing binary trees.  They are both partial functions;
that is they are (unary) functions which are undefined for atomic arguments.
%3car%* returns as value the first subexpression of its (composite) argument; %3cdr%* 
(pronounced could-er) returns as vlue the second sub-expression of its
argument.  For example:
.GROUP SKIP 2;
.BEGIN INDENT 10; TABS 30;TURN ON "\,←";NOFILL;
.GROUP;
%3car[(A . B)] = A\car[A] %*is undefined.
%3cdr[(A . B)] = B\cdr[A(A . (B . C))] = (B . C)
←car[((A . B) . C)] = (A . B)
%*
.APART;
.END;
.GROUP SKIP 1;
.GROUP;
As with most mathematical theories, we will allow functional composition.
.BEGIN INDENT 0;TURN ON "←";nofill;
%3
←car[cdr[(A . (B . C))]] = B = cdr[cdr[(A . (C . B))]]
←car[cons[x;y]] = x     cdr[cons[x;y]] = y .
%*
.END;
.APART

Notice that in the last two examples we have introduced variables (over
S-exprs).  In the sequel lower-case letters (or lower-case identifiers) will be
used freely as (sexpr) variables.  So for example %3Y%* is an atom; %3x%* is a variable
The composition of many %3car%* and %3cdr%* functions occurs so frequently that an
abbreviation has been developed.  
.GROUP SKIP 2;
.BEGIN NOFILL;TURN ON "←";DOUBLE SPACE;
.GROUP;
For example:
%3
←cadr[x] ≡ car[cdr[x]]
←caddr[x] ≡ car[cdr[cdr[x]]]
←cdar[x] ≡ cdr[car[x]]
%*
.end;

These compositions are also called "%3car-cdr%*" chains, and are useful in
traversing binary trees.
We cannot generate a very exciting theory based simply on %3car, cdr,%* and %3cons
%*
with functional composition. Before we can write reasonably interesting 
algorithms we must have some way of performing conditional actions;
an IF-THEN-ELSE facility if you wish.  To do this we need predicates:  functions
returning a value representing truth or falsity.  Since our functions
return Sexprs as values we must represent truth and falsity as Sexprs.
We will take the atoms %3T%* and %3NIL%* to represent true and false, respectively.
Now two predicates. The first is a total predicate named %3atom%*.  It is a predicate
of one argument returning, %3T%* or %3NIL%* depending on whether or not that
argument is atomic.
.BEGIN NOFILL;TURN ON "←";
.GROUP
%3
←atom[A] ≡ atom[NIL] = T
←atom[atom[A]] = T = atom[atom[(A . B)]]
%*
.APART
.END

The second primtive predicate is named %3eq%*.  It is a binary predicate defined
only if its arguments are both atomic.  It returns %3T%* if the arguments are the
same atom; it returns %3NIL%* otherwise.
.BEGIN NOFILL;TURN ON "←";
%3
.GROUP SKIP 1;
.GROUP
←eq [A;A] = T			eq [A;B] = NIL
←eq [(A . B); A] %* is undefined, as is  %3eq [(A . B);(A . B)]
←eq [eq [A;B];eq [C;D]] = T
%*
.APART;
.END

The IF-THEN-ELSE operation in LISP is called the condition expression.  It
is written:
.BEGIN NOFILL;TURN ON "←";
%3
←[p%41%* → e%41%*; p%42%* → e%42%*  ... ; p%4n%*  → e%4n%*]
%1
.END

The meaning (or semantics) of conditionals is:  Each %3p%4i%1 is a predicate; 
each %3e%4i%1
is an expression.  We evaluate the %3p%4i%1 's from left to right, finding the first
which returns value %3T%*.  When we find such a %3p%4i%1 , we evaluate the corresponding
%3e%4i%1.  The value of the conditional expression the value returned by %3e%4%1; if none
of the %3p%4i%1's are true then the conditional expression is undefined.  The
conditional expression is also undefined if we come across a %3p%4i%1
which is undefined.  
.BEGIN NOFILL;TURN ON "←";
.GROUP;
Examples:

%3
←[atom [A] → B; eq [A;(A . B)] → C] = B
←[eq [A;(A . B)] → C; atom [A] → B] is undefined
←[atom [(A . B)] → B; eq [A ; B] → C; eq [car[(A . B)]; cdr[(B . A)]] → E] = E
%1
.APART
.END


In applications of conditional expressions it is often convenient to be
assured that the conditional always is defined.  To make sure that at least one of
the %3p%4i%1's is true we can pick a predicate for %3p%4n%1, (the last predicate in the 
conditional) which is always true.  You can think of lots of predicates which
are always true ( for example, %3eq [1;1]%* ).  A natural predicate is the
constant predicate, %3T%*.  Thus:
.GROUP

.BEGIN NOFILL;TURN ON "←";

%3
←[p%41%*  → e%41%*; T → e%42%*]
%1
.END
can be read:  If %3p%41%1  is true then  %3e%41%1  else %3e%42%1.  (or otherwise %3e%42%1)

.APART;
A word to the wise.  It doesn't seem like you can do much damage with such
a limited collection of operations.  %6Do not be deceived!%*  In elementary number
theory all you have is zero and some simple functions, and elementary number theory
is far from elementary.

For example: our predicate %3eq%* is defined only for atomic arguments.  We would like
to be able to test for equality of arbitrary sexprs.  For example, we would
like to define a predicate, %3equal%*, such that:
.GROUP SKIP 1;
.GROUP
.BEGIN NOFILL;TURN ON "←";
%3
←equal [(A . B);(A . B)] = T = equal [A,A]
←equal [(A . B);(B . A)] = NIL 
←equal [(A . (B . C));(A . (B . C))] = T

%1
.END
.APART
Here's an intuitive description of such a function (predicate named %3equal%*).

1.  if both arguments are atomic then see what %3eq%* says about them
(are they "%3eq%*").  We make sure that they are both atomic by using %3atom%*
and a conditional expression.

2.  If one is atomic and the other is not they can't be equal s-exprs.

3.  Otherwise both are non-atomic sexprs.  Both have two sub-expressions.

Look at both first subexpressions.  If the first sub-expressions are not
equal then certainly the initial expressions cannot hope to be equal.  
However, if the first subexpressions are equal then the question of
whether or not the initial expressions are equal depends on the
equality ( or non-equality) of the second subexpressions.  Thus the
following definition:
.GROUP
%3
.BEGIN NOFILL;TABS 19,30;TURN ON "\";

equal[x,y] <=\[atom[x] → [atom[y] → eq [x;y]
\\ T→ NIL];
\ atom[y] → NIL;
\ equal [car[x];car[y]] → equal[cdr[x];cdr[y]];
\ T → NIL]

.END
.APART
%1
.GROUP
.BEGIN TURN ON "←";
%2
←List Notation
%1
.END

In many applications of LISP it will be very convenient to represent
sequences.  E.g. %3(x%41%*, x%42%*, x%43%*)%1.  We will allow sequences to have
sub-sequences (to an arbitrary depth) e.g. %3(A,(B,C),D,(E,B))%*.  The obvious
question is how to represent sequences as Sexprs.  Since sequences can be of
arbitrary length any representation must include an unambiguous way of
determining the end of such a sequence.
.APART
.GROUP
The choice we make is represented graphically as follows:
%3
.BEGIN VERBATIM


	                                             ≡ (X  . (Y  . (Z  . NIL)))

X		Y		Z      NIL

.END
.APART
%1

Note that we can determine the end of the sequence using the predicate:

.BEGIN NOFILL;TURN ON "←";
%3
←endofseq[x] = [atom[x] → eq[x,NIL]; T → NIL]
%1
.END

That is the right-hand branch in any binary tree representing a sequence
will always point to the rest of the sequence or will be the atom %3NIL%*.  It
is not by accident that the atom %3NIL%* is used for falsity and the termination
symbol for sequences.  You should become fluent in translating between
sexpr-notation and sequence notation.

In standord Computer Science terminology sequences are called lists, thus we
will refer usually to list-notation list terminator, etc.  You should also
become fluent in applying our basic functions to lists without having to
translate back to sexpr-notation.

A final point:  what about the empty sequence or empty list? Looking at the
graphical interpretation of a sequence it appears natural to take %3NIL%* as
the empty list since after you have removed all the elements from the list,
%3NIL%*, the list terminator is all that is left.  Also from the standpoint of
sequence notation, the empty sequence is represented as:  "%3( )%*".  To be
consistent, then, we will define %3( )%* to be the same as the atom %3NIL%*.  And
a notational point:  in graphical notation it is often convenient to write
.GROUP
.BEGIN NOFILL;TURN ON "\";TABS 10,30;

\\as                  .  

\       %3NIL%*
.END
.APART
%1
.BEGIN NOFILL;TURN ON "\,←";TABS 20,30,40;
.GROUP
Thus, for example:

←%3(A,(B,C),D)%* is:



%3
\A\\    D



\\   B\   C

%1
or:
%3

←A








←B    C    NIL     D    NIL 
%1

.END
.APART
Finally in list-notation, the commas can be replaced by spaces.
.BEGIN NOFILL;TURN ON "←";
%3

←e.g. (A,(B,C),D) ≡ (A(B C)D).
%1
.END
Note:  the "dots" in dot-notation are never optional.

.NEXT PAGE
.BEGIN TURN ON "←,\";NOFILL;TABS 10;
←%2Problems %1
.GROUP SKIP 2;
I Which of the following are dotted-pairs.
\%21.%3 (X . Y)   %22.%3 ((A .(B . C))  %23.%3  A2   %24.%3 (X . Y2 . Z)
.GROUP SKIP 2;
%1
II Write the following as binary trees.
\%21.%3  ((A . B).(B . (C . D)))  %22.%3  (A . B).C).E)
\%23.%3  ((X . NIL).(Y .(Z . NIL)))    %24.%3  (NIL . NIL)
.GROUP SKIP 2;
%1
.GROUP
III Write the following binary trees as Sexprs.
.END
.BEGIN NOFILL;TURN ON "\";TABS 10;

\%21.              2.                       3.        
\%3                    A  
\  A 
\     B  C                                  A 

\			  B

\			                          B

\		 C   NIL       D    E  

\						     C  NIL



.APART
.GROUP
%2
\4.                                5.
%3
\    CAR            NIL 

\	                            CONS        X         Y  NIL


\		    QUOTE         A    NIL

.APART
.END
%1
.GROUP
IV Evaluate the following

.BEGIN TURN ON "←,\";TABS 40;
←%21.%3 eq[X;Y]   %22.%3 cons[X;Y]   %23.%3 car[(X . Y)]   %24.%3 car[cons[X;Y]]

%25.%3 cadr[(X .(Y . NIL))]   \%26.%3 cdar[(X .(Y . NIL))]

%27.%3 eq[cdr[(A . B)];cdr[(C . B)]]   \%28.%3 atom[cons[(A . B);(C . D)]]

%29.%3 cons[atom[A];atom[(A . B)]]   \%210.%3 eq[atom[ATOM];atom[EQ]]

←%211.%3 [T → A; T → B]   %212.%3 [NIL → A; T → B]   %213.%3 [eq[A;B] → 4]

%214.%3 [atom[X] → atom[X]; T → FOO]   \%215.%3 [eq[EQ;X] → A; eq[A;B] → B; T → C]

←%216.%3 cons[[eq[A;B] → 1; T → FOO];cons[A;cadr[(A .(B .C))]]]
.END

.APART
%1
.GROUP
V  Use the following definition:
.BEGIN NOFILL;TURN ON "←,\";TABS 10,23;

%3
\  twist[s] <=\[atom[s] → s;
\\ T → cons[twist[cdr[s]];twist[car[s]]]]
%1

and evaluate: 
%21.%3 twist[A]   %22.%3 twist[(A . B)]   %23.%3 twist[((A . B). C)]
.APART
.GROUP

%1
Now try:
%3
\findem[x;y] <=\[atom[x] → [eq[x;y] → T; T → NIL];
\\ T → cons[findem[car[x];y];findem[cdr[x];y]]]
%1

and evaluate:
%21.%3 findem[(A . B);A]   %22.%3 findem[(B .(A . C));A]
%23.%3 findem[(B .(A . C));C]   %24.%3 findem[(A . B);(A . B)]
.APART
.GROUP
%2

←Problems involving list-notation
%1

VI  Translate the following lists into Sexpr dotted-pair notation.
←%21.%3 (A B C)   %22.%3 (A)   %23.%3 ((A))   %24.%3 (A (B (C))).

.APART
.GROUP
%1

Now go the other way and translate the following sexprs into list notation.
←%25.%3 ((A .(B . NIL)).((C . NIL). NIL))   %26.%3 (NIL . NIL)
←%27.%3 ((CONS .((QUOTE .(A . NIL)). NIL))
.APART
.GROUP
%1

VII  Evaluate the following, writing the results in list notation where possible.
←%21.%3 car[(A B)]   %22.%3 cdr[(A B)]   %23.%3 cons[A;(B C)]   %24.%3 cons[A;NIL]
←%25.%3 cons[eq[A;A];(A B C)]

.APART
.GROUP
%1
VIII  Use the following defintion:
%3
\match[k;m] <=\[null[k] → NO;
\\ null[m] → NO;
\\ eq[car[k];car[m]] → car[k];
\\ T → match[cdr[k];cdr[m]]]

%1
and evaluate:
%21.%3 match[(X);(X)]   %22.%3 match[(A B E);(J O E)]  %23.%3 match[(F O O); (BAZ)]
.APART
.END
%1
.GROUP

.BEGIN TURN ON "\";TABS 10;
IX  Now write your own.

%21.%3 among[x;y] <= ... : among%1 is to be a predicate; %3x%1 is an atom; %3y%1 is a list
of atoms.  %3among%1 is to return %3NIL%1 if %3x%1 is not found as an element of %3y%1; o.w.
among is to return %3T%1.

.NOFILL
\e.g. %3among[A;(A B C)] = among[A;(C D E A)] = T
\     among[A1;(A2 B2)] = NIL.
.FILL
%1

%22.%3 anywhere[x;y] <= ... : anywhere%1 is a predicate; %3x%1 is an atom; %3y%1 is an arbitrary
sexpr. %3anywhere%1 is to return %3T%1 just in the case that %3x%1 appears somewhere in %3y%1.
.NOFILL

\e.g. %3anywhere[A;(A B C)] = anywhere[A;((A . B). C)] = T
\     anywhere[A;(B C D)] = NIL.
.FILL
%1

.END
.BEGIN TURN ON "←,\";NOFILL;TABS 10,25,36;

.GROUP;
←%2I. The Great Mother of All Functions!!! (%3tgmoaf%*)
%3

\tgmoaf[x] <= \[atom[x] →\[eq[x ;T] → T;
\\\ eq[x;NIL] → NIL;
\\\ T → TRYAGAINNEXTWEEK];
\\ eq[car[x];QUOTE] → cadr[x];
\\ eq[car[x];CAR] → car[tgmoaf[cadr[x]]];
\\ eq[car[x];CDR] → cdr[tgmoaf[cadr[x]]];
\\ eq[car[x];CONS] → cons[tgmoaf[cadr[x]];tgmoaf[caddr[x]]];
\\ eq[car[x];ATOM] → atom[tgmoaf[cadr[x]]];
\\ eq[car[x];EQ] → eq[tgmoaf[cadr[x]];tgmoaf[caddr[x]]];
\\ T → TRYAGAINNEXTWEEK]
%1
.APART
.GROUP

Evaluate the following:

%21.%3 tgmoaf[T]
%22.%3 tgmoaf[A]
%23.%3 tgmoaf[(CAR(QUOTE(A . B)))]
%24.%3 tgmoaf[(CDR (QUOTE (A B)))]
%25.%3 tgmoaf[(EQ (CAR (QUOTE (A . B)))(QUOTE A))]
%26.%3 tgmoaf[(EQ (CAR (QUOTE (A . B))) A)]
%27.%3 tgmoaf[(ATOM (CAR (QUOTE (A B))))]
.APART

.GROUP


←%2II. The Great Mother of All Functions Revisited!!!(%3tgmoafr%*)
%3

\tgmoafr[x] <= \[atom[x] →\[eq[x;T] → T;
\\\ eq[x;NIL] → NIL;
\\\ T → TRYAGAINNEXTWEEK];
\\ eq[car[x];QUOTE] → cadr[x];
\\ eq[car[x];CAR] → car[tgmoafr[cadr[x]]];
\\ eq[car[x];CDR] → cdr[tgmoafr[cadr[x]]];
\\ eq[car[x];CONS] → cons[tgmoafr[cadr[x]];tgmoafr[caddr[x]]];
\\ eq[car[x];ATOM] → atom[tgmoafr[cadr[x]]];
\\ eq[car[x];COND] → evcond[cdr[x]];
\\ T → TRYAGAINNEXTWEEK]
.APART
.GROUP

\evcond[x] <=\[tgmoafr[caar[x]] → tgmoafr[cadar[x]];
\\ T → evcond[cdr[x]] ]
.APART
.GROUP
%1

Evaluate the following:

%21.%3 tgmoafr[T]
%22.%3 tgmoafr[(CDR (QUOTE (A B)))]
%23.%3 tgmoafr[(EQ (CAR (QUOTE (A . B))) (QUOTE A))]
%24.%3 tgmoafr[(COND((EQ (CAR (QUOTE (A . B)))(QUOTE A))(QUOTE FOO)))]
%25.%3 tgmoafr[(COND((ATOM (QUOTE (A)))(QUOTE FOO))(T(QUOTE BAZ)))]
.APART
.END
.BEGIN TURN ON "←,\";TABS 10;

.GROUP
←%2Problems involving %3prog.
%1

Write %3prog%*-versions of the following functions (or predicates).

%21.%3 member[x;y]<= ... : x%1 is atomic; %3y%* is a list of atoms.  %3member%* is to 
return %3T%* just in the case that %3x%* is one of the elements in %3y%*.
.APART

%22.%1 The factorial funciion.

%23.%3  delete[x;y]<= ... : x%1 is atomic; %3y%* is a list of atoms.  %3delete%* is to 
return a list which looks like %3y%*, except all occurrences of %3x%*
have been deleted.

%24.%1 The %3append%* function.

%25.%3  last[x]<= ... : x%1 is a non-empty list.  %3last%* is to return the last 
element in %3x%*.

%26.%1  Now write the Sexpr translations of each of your functions.
.GROUP


←%2Hacking with %3eval%* and friends.
%1

Assume that the variable, %3st%1, is currently bound to:
.NOFILL
←%3((X . M)(Y . T)(Z .(M N))(T . T)).
%1

evaluate:

%21.%3 assoc[Z;st]
.APART
%22.%3 eval[(QUOTE A);st]
%23.%3 apply[CONS;(A B); st]
%24.%3 apply[CAR;((A));st]
%25.%3 apply[CAR;(A);st]

.FILL
.END